package com.sheng.leetcode.year2023.month01.day17;

import org.junit.Test;

import java.util.HashMap;

/**
 * @author liusheng
 * @date 2023/01/17
 * <p>
 * 1814. 统计一个数组中好对子的数目<p>
 * <p>
 * 给你一个数组 nums ，数组中只包含非负整数。定义 rev(x) 的值为将整数 x 各个数字位反转得到的结果。比方说 rev(123) = 321 ，<p>
 * rev(120) = 21 。我们称满足下面条件的下标对 (i, j) 是 好的 ：<p>
 * 0 <= i < j < nums.length<p>
 * nums[i] + rev(nums[j]) == nums[j] + rev(nums[i])<p>
 * 请你返回好下标对的数目。由于结果可能会很大，请将结果对 10^9 + 7 取余 后返回。<p>
 * <p>
 * 示例 1：<p>
 * 输入：nums = [42,11,1,97]<p>
 * 输出：2<p>
 * 解释：两个坐标对为：<p>
 * - (0,3)：42 + rev(97) = 42 + 79 = 121, 97 + rev(42) = 97 + 24 = 121 。<p>
 * - (1,2)：11 + rev(1) = 11 + 1 = 12, 1 + rev(11) = 1 + 11 = 12 。<p>
 * <p>
 * 示例 2：<p>
 * 输入：nums = [13,10,35,24,76]<p>
 * 输出：4<p>
 * <p>
 * 提示：<p>
 * 1 <= nums.length <= 10^5<p>
 * 0 <= nums[i] <= 10^9<p>
 * <p>
 * 来源：力扣（LeetCode）<p>
 * 链接：<a href="https://leetcode.cn/problems/count-nice-pairs-in-an-array">1814. 统计一个数组中好对子的数目</a><p>
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。<p>
 */
public class LeetCode1814 {

    @Test
    public void test01() {
        int[] nums = {42, 11, 1, 97};
//        int[] nums = {13, 10, 35, 24, 76};
        System.out.println(new Solution().countNicePairs(nums));
    }
}

/**
 * 首先题目给出一个下标从 0 开始长度为 n 的非负整数数组 nums，并给出「好下标对」的定义——对于某一个下标对 (i, j)，0 ≤ i < j < n，若满足：
 * nums[i] + rev(nums[j]) = nums[j] + rev(nums[i])      (1)
 * 则该下标对为「好下标对」。现在我们设：f(i) = nums[i] − rev(nums[i])，则表达式 (1) 可以等价于：
 * f(i) = f(j)      {2}
 * 那么我们从左到右遍历数组 nums，并在遍历的过程用「哈希表」统计每一个位置 i，0 ≤ i < n 的 f(i) 的个数，则对于位置 j，0 ≤ j < n，
 * 以 j 结尾的「好下标对」的个数为此时「哈希表」中 f(j) 的数目。那么我们只需要在遍历时同时统计以每一个位置为结尾的「好下标对」数目即可。
 * <p>
 * 作者：LeetCode-Solution
 * 链接：<a href="https://leetcode.cn/problems/count-nice-pairs-in-an-array/solution/tong-ji-yi-ge-shu-zu-zhong-hao-dui-zi-de-ywux/">...</a>
 * 来源：力扣（LeetCode）
 * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
 */
class Solution {
    public int countNicePairs(int[] nums) {
        int res = 0;
        HashMap<Integer, Integer> map = new HashMap<>(16);
        for (int num : nums) {
            int temp = num, j = 0;
            while (temp > 0) {
                j = j * 10 + temp % 10;
                temp /= 10;
            }
            res = (res + map.getOrDefault(num - j, 0)) % 1000000007;
            map.put(num - j, map.getOrDefault(num - j, 0) + 1);
        }
        return res;
    }
}
